#include <iostream>
#include <vector>
using namespace std;

template <class T>
struct Less{
  bool operator()(const T& left, const T& right)
  {
    return left < right;
  }
};

template <class T>
struct Greater{
  bool operator()(const T& left, const T& right)
  {
    return left > right;
  }
};

template <class T, class Compare>
void insert_sort(vector<T> &arr, Compare comp){
  for(size_t i = 0; i<arr.size()-1; ++i)
  {
    int end = i;
    T x = arr[end+1];
    while(end >= 0)
    {
      if(comp(x, arr[end]))
      {
        arr[end+1] = arr[end];
        --end;
      }
      else{
        break;
      }
    }
    arr[end+1] = x;
  }
}

template <class T, class Compare>
void shell_sort(vector<T> &arr, Compare comp){
  int gap = arr.size();
  while(gap > 1)
  {
    gap = gap/3+1;
    for(int i = 0; i<arr.size()-gap; ++i)
    {
      int end = i;
      T x = arr[end+gap];
      while(end>=0)
      {
        if(comp(x,arr[end]))
        {
          arr[end+gap] = arr[end];
          end-=gap;
        }
        else{
          break;
        }
      }
      arr[end+gap] = x;
    }
  }
}

int main(){
  int arr1[] = {1,4,3,6,2,5,8,7};
  char arr2[] = "abdecgfk";
  double arr3[] = {1.1,3.5,2.6,2.9,3.8,5.5,3.14,4.58};
  vector<double> vc(arr3, arr3+8);
  for(auto e:vc)
  {
    cout << e <<" ";
  }
  cout << endl;

  shell_sort(vc,Less<double>());
  for(auto e:vc)
  {
    cout << e <<" ";
  }
  cout << endl;
  
  shell_sort(vc,Greater<double>());
  for(auto e:vc)
  {
    cout << e <<" ";
  }
  cout << endl;
}
